package day05;

import java.util.HashSet;
import java.util.Set;


public class 相交链表 {
    /*public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 利用哈希表存储每个节点
        Set<ListNode> set = new HashSet<>();
        // 先遍历链表A
        while(headA != null){
            set.add(headA);
            headA = headA.next;
        }
        // 遍历链表B
        while(headB != null){
            // 进行判断
            if(!set.contains(headB)){
                // 进行添加
                set.add(headB);
            }else{
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }*/

    //6.26提交

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 先求两个链表的长度
        int lenA = 0;
        int lenB = 0;
        // 规定cur1永远指向最长的呢个
        ListNode cur1 = headA;
        while(cur1 != null){
            lenA++;
            cur1 = cur1.next;
        }
        // 规定cur2永远指向最短的呢个
        ListNode cur2 = headB;
        while(cur2 != null){
            lenB++;
            cur2 = cur2.next;
        }
        int len = lenA - lenB;
        cur1 = headA;
        cur2 = headB;
        // 进行len 大小的判断
        if(len < 0){
            cur1 = headB;
            cur2 = headA;
            len = lenB - lenA;
        }
        // 此时cur1指向最长的呢个，cur2指向最短的呢个
        // 先让最长的呢个走len步
        while(len-- != 0){
            cur1 = cur1.next;
        }
        // 利用双指针进行比较
        // 因为此时两个链表的路程是一样的
        while(cur1 != null && cur1 != cur2){
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        // 进行判断
        if(cur1 != null){
            return cur1;
        }
        return null;
    }
}
